"""1. 分治法解决大整数乘法（Karatsuba算法）"""
def karatsuba_multiply(x, y):
    """
    Karatsuba算法 - 分治法解决大整数乘法
    时间复杂度: O(n^log2(3)) ≈ O(n^1.585)
    """
    # 将整数转换为字符串以便处理
    x_str = str(abs(x))
    y_str = str(abs(y))

    # 确定符号
    sign = -1 if (x < 0) ^ (y < 0) else 1

    # 基本情况：如果数字很小，直接相乘
    if len(x_str) == 1 or len(y_str) == 1:
        return sign * (abs(x) * abs(y))

    # 确保两个数字位数相同（补零）
    n = max(len(x_str), len(y_str))

    # 如果位数是奇数，调整为偶数
    if n % 2 != 0:
        n += 1

    # 补零使两个数字位数都为n
    x_str = x_str.zfill(n)
    y_str = y_str.zfill(n)

    # 分割数字
    mid = n // 2
    a = int(x_str[:mid])  # 高位部分
    b = int(x_str[mid:])  # 低位部分
    c = int(y_str[:mid])  # 高位部分
    d = int(y_str[mid:])  # 低位部分

    # 递归计算三个乘积
    ac = karatsuba_multiply(a, c)  # a*c
    bd = karatsuba_multiply(b, d)  # b*d
    # (a+b)*(c+d) = ac + ad + bc + bd
    ad_plus_bc = karatsuba_multiply(a + b, c + d) - ac - bd

    # 合并结果：ac * 10^(2m) + (ad+bc) * 10^m + bd
    result = ac * (10 ** (2 * mid)) + ad_plus_bc * (10 ** mid) + bd

    return sign * result


def school_method_multiply(x, y):
    """
    传统学校方法（竖式乘法）
    时间复杂度: O(n²)
    """
    x_str = str(abs(x))
    y_str = str(abs(y))
    sign = -1 if (x < 0) ^ (y < 0) else 1

    result = 0
    n = len(y_str)

    # 模拟竖式乘法
    for i in range(n):
        digit = int(y_str[n - 1 - i])
        partial = abs(x) * digit * (10 ** i)
        result += partial

    return sign * result


# 测试大整数乘法
print("=== 大整数乘法测试 ===")
test_cases = [
    (1234, 5678),
    (123456789, 987654321),
    (999999, 999999),
]

for x, y in test_cases:
    expected = x * y
    karatsuba_result = karatsuba_multiply(x, y)
    school_result = school_method_multiply(x, y)

    print(f"{x} × {y} = {expected}")
    print(f"Karatsuba算法: {karatsuba_result} (正确性: {karatsuba_result == expected})")
    print(f"传统方法: {school_result} (正确性: {school_result == expected})")
    print()